/*
 * @lc app=leetcode.cn id=134 lang=cpp
 * @lcpr version=30204
 *
 * [134] 加油站
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalTank = 0; // 总油量
        int currTank = 0;  // 当前油量
        int start = 0;     // 起始加油站

        for (int i = 0; i < gas.size(); ++i) {
            totalTank += gas[i] - cost[i];
            currTank += gas[i] - cost[i];
            // 如果当前油量不足，更新起点为下一个加油站
            // 这里的道理是如果从 start 开始无法到达 i，那么从 start 到 i 之间的所有加油站都不能作为起点
            // 因为中间累计剩余的油量只有从start到i是最多的，现在连这这个都不行，那么只能从后面的点选取作为起点
            if (currTank < 0) {
                start = i + 1;
                currTank = 0; // 重置当前油量
            }
        }

        // 如果总油量不足，无法完成环路
        return totalTank >= 0 ? start : -1;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [1,2,3,4,5]\n[3,4,5,1,2]\n
// @lcpr case=end

// @lcpr case=start
// [2,3,4]\n[3,4,3]\n
// @lcpr case=end

 */

